package tsVRPTW;

import static java.lang.Math.*;
import static tsVRPTW.Parameter.*;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;

import tsVRPTW.CustomerType;

import static tsVRPTW.EvaluateRoute.*;

/**
 * 1. Distance(CustomerType c1, CustomerType c2)计算图中节点之间的距离 2. ReadIn() 初始化 3.
 * Construction() 构造初始解 4. Output() 输出最优解 5. Check_Ans() 验证距离与时间约束
 *
 * @author cxd15
 */
public class InitAndPrint {

    //	计算图中节点之间的距离
    private static double Distance(CustomerType c1, CustomerType c2) {
        return sqrt((c1.X - c2.X) * (c1.X - c2.X) + (c1.Y - c2.Y) * (c1.Y - c2.Y));
    }

    /**
     * 1.初始化客户节点数组，路径数组，最优路径数组
     * 2.读取客户数据
     * 3.初始化每条车辆的路径（起始仓库，终点仓库，路径负载）
     * 4.计算两点之间距离，存储进Graph[][] 数组中
     */
    public static void ReadIn() {

//		1. 初始化客户节点数组，路径数组，最优路径数组
        for (int i = 0; i < CustomerNumber + 10; i++) {
            customers[i] = new CustomerType();
        }
        for (int i = 0; i < VehicleNumber + 10; i++) {
            routes[i] = new RouteType();
            route_Ans[i] = new RouteType();
        }

//		2. 开始读取客户数据
        try {
            Scanner in = new Scanner(new FileReader("F:\\workspace\\VRP\\bin\\tsVRPTW\\c101.txt"));
            for (int i = 1; i <= CustomerNumber + 1; i++) { // 将仓库作为客户节点加入
                customers[i].Number = in.nextInt() + 1; // 客户的编号从0开始
                customers[i].X = in.nextDouble();
                customers[i].Y = in.nextDouble();
                customers[i].Demand = in.nextDouble();
                customers[i].Begin = in.nextDouble();
                customers[i].End = in.nextDouble();
                customers[i].Service = in.nextDouble();
            }

            in.close();
        } catch (FileNotFoundException e) {
            System.out.println("File not found!!!");
            System.exit(-1); // 0代表正常退出，-1代表非正常退出
        }

//		3. 初始化每条车辆的路径（起点仓库，终点仓库，路径负载）
        for (int i = 1; i <= VehicleNumber; i++) {
            if (routes[i].V.size() != 0) {
                routes[i].V.clear();
            }
            routes[i].V.add(new CustomerType(customers[1])); // 以仓库为起点
            routes[i].V.add(new CustomerType(customers[1])); // 以仓库为终点
            routes[i].V.get(0).End = routes[i].V.get(0).Begin; // 起点仓库的时间窗结束时间等于开始时间
            routes[i].V.get(1).Begin = routes[i].V.get(1).End; // 终点仓库的时间窗开始时间等于结束时间
            routes[i].Load = 0; // 每条路径初始负载为0
        }

//		4. 计算两点之间距离（应该从0开始，把仓库也包含在内）
        for (int i = 1; i <= CustomerNumber; i++) {
            for (int j = 1; j <= CustomerNumber; j++) {
                Graph[i][j] = Distance(customers[i], customers[j]);
            }
        }
    }

    /**
     * 构造初始解
     * 1. 随机抽出客户C，在满足容量约束的条件下，插入到合适的路径中Current_Route
     * 2.在路径Current_Route中，根据时间窗开始时间约束，插入到相应位置
     * 3.在将所有客户都插入完毕之后，更新总的所有路径的时间窗违反量（这里不用考虑路径载量约束违反量，因为此时没有超出载量约束）
     */
    public static void Construction() {

        // 0.初始化
        Ans = INF; // 初始解的，最有距离。定义为一个尽量大的数
    	// 创建客户编号数组，数组值为客户的编号
        int[] Customer_Set = new int[CustomerNumber + 10];
        for (int i = 1; i <= CustomerNumber; i++) {
            Customer_Set[i] = i + 1;
        }
        int Sizeof_Customer_Set = CustomerNumber; // 客户的数量
        int Current_Route = 1; // 从第0条路径开始（路径数组的索引，这里从1开始仅仅是为了看起来方便）

        // 1.将所有的访问点安排到路径中
		// 从customers数组中随机抽出一个客户，插入到路径中。若已超过当前路径的容量约束，则插入下一条路径中。
		// 路径中的插入位置，由路径中已存在的各节点时间窗的最早开始时间决定
        while (Sizeof_Customer_Set > 0) { // 直到所有的客户节点都被安排完毕

			// 1.1 不重复随机抽取客户编号
			// 在当前未安排完毕的客户数量内，随机抽取一个数，作为客户编号数组中的索引K
            int K = (int) (random() * Sizeof_Customer_Set + 1); // 因为(int)是向下取整，所以必须要加1
			// 客户编号数组中索引K对应的值，即为随机抽取到的客户编号
			// 在客户编号数组中抽出该客户编号后，将数组中最后一个元素放在该位置，并将随机范围减1
            int C = Customer_Set[K];
            Customer_Set[K] = Customer_Set[Sizeof_Customer_Set];
            Sizeof_Customer_Set--;

			// 1.2 选择一条满足容量约束的路径（尝试将此节点插入其中）
            if (routes[Current_Route].Load + customers[K].Demand > Capacity) {
                Current_Route++;
            }

			// 1.3 根据时间窗约束，查找此路径中的合适位置，并将访问点插入其中。
            // 对路径中每一个节点查找，找到可以插入的位置（C的开始时间不早于i，不晚于i+1）
            for (int i = 0; i < routes[Current_Route].V.size() - 1; i++) {
                if ((routes[Current_Route].V.get(i).Begin <= customers[C].Begin)
                        && (customers[C].Begin <= routes[Current_Route].V.get(i + 1).Begin)) {

                    routes[Current_Route].V.add(i + 1, new CustomerType(customers[C])); // 将客户C加入到路径中
                    routes[Current_Route].Load += customers[C].Demand; // 增加路径负载
                    customers[C].R = Current_Route; // 客户C在路径Current_route中
                    break; // 此客户安排完成，安排下一个客户
                }
            }
        }

		// 2.更新初始解对时间窗约束量的总违反量
        for (int i = 1; i <= VehicleNumber; i++) {
            routes[i].SubT = 0;
            routes[i].Dis = 0;
            for (int j = 1; j < routes[i].V.size(); j++) {
                routes[i].Dis += Graph[routes[i].V.get(j - 1).Number][routes[i].V.get(j).Number];
            }
            UpdateSubT(routes[i]);
        }
    }

    //	输出计算结果
    public static void Output() {
        System.out.println("****************************************************************");
        System.out.println("The Minium Total Distance is: " + Ans);
        System.out.println("Concrete Schedule of Each Route as Following:");

        int M = 0; // 作为索引下标
        for (int i = 1; i <= VehicleNumber; i++) {
            if (route_Ans[i].V.size() > 2) {
                M++;
                System.out.print("No. " + M + ": ");
                for (int j = 0; j < route_Ans[i].V.size() - 1; j++) {
                    System.out.print(route_Ans[i].V.get(j).Number + " -> ");
                }
                System.out.println(route_Ans[i].V.get(route_Ans[i].V.size() - 1).Number);
            }
        }
        System.out.println("****************************************************************");
    }

    //	验证距离，与时间窗约束
    public static void Check_Ans() {

//		距离计算的验证
        double Check_Ans = 0;
        for (int i = 1; i <= VehicleNumber; i++) {
            for (int j = 1; j < route_Ans[i].V.size(); j++) {
                Check_Ans += Graph[route_Ans[i].V.get(j - 1).Number][route_Ans[i].V.get(j).Number];
            }
        }
        System.out.println("Check_Ans = " + Check_Ans);

//		时间窗约束
        boolean flag = true; // 默认满足时间窗约束
        for (int i = 1; i <= VehicleNumber; i++) {
            UpdateSubT(route_Ans[i]);
            if (route_Ans[i].SubT > 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            System.out.println("Solution satisfies time windows constructions");
        } else {
            System.out.println("Solution not satisfies time windows constructions");
        }
    }
}